1. Field of the Invention
This invention relates generally to the area of error detection for digital computer systems and more specifically to parity prediction logic for high-speed binary adders with shifting outputs.
2. Description of the Prior Art
A binary adder is a vital component of electronic digital computer systems. The speed and reliability of the binary adder are, therefore, major concerns in computer system design. It is well known that a carry look-ahead adder generates the result of an operation on two operands faster than that of a ripple carry adder. It is also known that a carry look-ahead adder can be implemented in many different ways. This invention is not concerned with design of a high-speed binary adder, but rather relates to the design of checking logic for error detection in a high speed adder. For an explanation of the operation of carry-look-ahead adders, see Langdon and Tang, "Concurrent Error Detection for Group-Look Ahead Adders," IBM Tech. Rep., TR 01.1200, Aug. 26, 1969.
In the past, computers were used largely in an off-time, batch-processing mode and the consequences of undetected hardware malfunctions were relatively minor. Today, digital computers, even main-frame computers, are utilized in on-line information processing, data entry and retrieval, and real-time control of processes. Incorrect computer operation in any of these applications must be detected as soon as possible. At the same time, the increased size and complexity of digital computers have made it more and more difficult to ensure correct machine operation.
In modern computer systems, operational reliability is supported by built-in error detection. A commonly used method of error detection is parity checking. Conventionally, in a parity checking procedure, a "parity" bit is generated in response to the number of "ones" in an arbitrary group of bits. Typically, for a byte, comprising eight bits of data, the parity bit will take on a digital value (1 or 0) which will make the sum of the ones in the combined group of nine bits odd, if odd parity applies, or even, if even parity.
In modern computer architecture, data are transferred or exchanged between architectural units in a standard format. For example, data is transferred in the form of sequences in multi-byte "words" in many contemporary architectures. It is the case that a parity bit accompanies each byte being transferred so that transfer of a four-byte word involves thirty-six bits.
When words are operated upon by computer elements, as, for example, in an adder, the parity bits are separated and separately treated. When two words are combined in an adder to produce a result word, parity bits must be generated for each byte of the result. Formerly, parity bits for the result word were generated when the word was available from the adder. In this case, the parity bits were generated by operating on the result. It is now standard practice to increase the speed of conventional adder operations by "predicting" parity bits for the results in a parity predict operation performed concurrently with the add operation. In such schemes, predicted parity is generated and then compared to the actual parity of the result word. If disparity is detected, an error signal generated by the comparison causes the adder to repeat its operation. If a second error is detected, it is assumed that the adder has malfunctioned.
Parity prediction schemes are shown in Louie, U.S. Pat. No. 3,925,647 and Kalandra et al, IBM TDB Vol. 23, No. 12 (5/81). These schemes include parity prediction circuits which are very complex and may cause more delay then the adder itself. Elimination of delay is important, particularly in pipelined processing systems. The parity prediction delays cause the system designer to be faced with a trade-off: allow the system to operate at the speed of the adder and provide for means to unravel the system errors caused by errors in the adder, or slow the system to allow for the delays of the parity prediction circuit.
Another parity prediction scheme is shown in Taylor, U.S. Pat. No. 3,911,261. However, the scheme of Taylor only provides a "best guess" predicted parity. The increased error and delays caused by inaccurate "guesses" are unacceptable in modern computing systems.
Parity prediction is further complicated by architectures which use a "shifting adder." A shifting adder provides a result which includes more bits than are actually used as the output result signal. A subset of the actual result signal is selected in response to a selection signal. The selection signal is generated from the instruction being executed. For example, an adder may provide an actual result word having thirty-four bits. A selection signal determines whether the thirty-two most significant bits or the thirty-two least significant bits are provided on the output port. This allows for the increased precision of a thirty-four bit add operation with the use of the more common thirty-two bit bus architecture, but complicates the task of parity prediction. Because the parity is to be provided for the thirty-two bit word on the adder output port, a parity prediction scheme must take into account that an entirely different parity bit is needed for each possible output word. This requires parity prediction circuits for each possible shift. The result, for the example given, is to double the required parity prediction circuitry. A more efficient and economical technique of parity prediction is provided by the described embodiments of this invention.